class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        for row in matrix:
            s = 0
            for r in range(len(row)):
                s += row[r]
                row[r] = s

        def transpose(mat):
            return [[row[c] for row in mat] for c in range(len(mat[0]) if len(mat) > 0 else 0)]
        
        self.matrix = transpose(matrix)

        for row in self.matrix:
            s = 0
            for r in range(len(row)):
                s += row[r]
                row[r] = s

        self.matrix = transpose(self.matrix)

    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        if len(self.matrix) == 0:
            return 0
            
        return self.matrix[row2][col2] - \
            (self.matrix[row2][col1-1] if col1-1 >= 0 else 0) - \
            (self.matrix[row1-1][col2] if row1-1 >= 0 else 0) + \
            (self.matrix[row1-1][col1-1] if row1-1>=0 and col1-1>=0 else 0)

matrix = []
numMatrix = NumMatrix(matrix)
print( numMatrix.sumRegion(2, 1, 4, 3) )
print( numMatrix.sumRegion(1, 1, 2, 2) )
print( numMatrix.sumRegion(1, 2, 2, 4) )